package com.leetcode.程序员面试金典.hard;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2021-08-20 13:30
 */
public class 面试题_04_09_二叉搜索树序列 {


  public static void main(String[] args) {
    TreeNode root = new TreeNode(2);
    root.left = new TreeNode(1);
    root.right = new TreeNode(3);

    Solution solution = new Solution();
    List<List<Integer>> lists = solution.BSTSequences(null);
    System.out.println(lists);

  }

  static
  class Solution {
    public List<List<Integer>> BSTSequences(TreeNode root) {

      List<List<Integer>> result = new ArrayList<>();
      LinkedList<Integer> currentPath = new LinkedList<>();
      LinkedList<TreeNode> candidates = new LinkedList<>();

      if (root != null) {
        candidates.add(root);
      }
      bfs(currentPath, candidates, result);
      return result;
    }

    private void bfs(LinkedList<Integer> currentPath, List<TreeNode> candidates, List<List<Integer>> result) {
      if (candidates.isEmpty()) {
        result.add(new LinkedList<>(currentPath));
        return;
      }

      for (TreeNode node : candidates) {
        currentPath.addLast(node.val);

        List<TreeNode> nextCandidates = new ArrayList<>();
        for (TreeNode candidate : candidates) {
          if (node != candidate) {
            nextCandidates.add(candidate);
          }
        }
        if (node.left != null) {
          nextCandidates.add(node.left);
        }
        if (node.right != null) {
          nextCandidates.add(node.right);
        }

        bfs(currentPath, nextCandidates, result);

        // 回溯
        currentPath.removeLast();
      }

    }

    /**
     * 可能节省空间，但是不易理解
     *
     * @param currentPath
     * @param candidates
     * @param result
     */
    private void bfs2(LinkedList<Integer> currentPath, LinkedList<TreeNode> candidates, List<List<Integer>> result) {
      if (candidates.isEmpty()) {
        result.add(new LinkedList<>(currentPath));
        return;
      }

      for (int i = 0; i < candidates.size(); ++i) {
        TreeNode node = candidates.get(i);
        currentPath.addLast(node.val);
        candidates.remove(i);
        if (node.left != null) {
          candidates.add(node.left);
        }
        if (node.right != null) {
          candidates.add(node.right);
        }

        bfs(currentPath, candidates, result);

        // 回溯
        currentPath.removeLast();
        candidates.add(i, node);
        if (node.right != null) {
          candidates.removeLast();
        }
        if (node.left != null) {
          candidates.removeLast();
        }
      }
    }
  }

}
